package com.搜索和回溯;

import java.util.LinkedList;
import java.util.List;

class Solution6 {
    LinkedList<List<Integer>> res=new LinkedList<>();// 存放所有满足条件的路径
    LinkedList<Integer> subset=new LinkedList<>();//存放正在寻找的路径
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        dfs(root,target,subset,res);
        return res;
    }
    void dfs(TreeNode root,int target,LinkedList<Integer> subset,LinkedList<List<Integer>> res){
        //终止条件
        if(root==null){
            return;
        }
        subset.add(root.val);
        // int sum=0;
        // for (int e:subset) {
        //     sum+=e;
        // }
        //改进上面发for循环
        target-=root.val;
        if(target==0&&root.left==null&&root.right==null){
            res.add(new LinkedList<>(subset));//找到一条满足条件的路径，将其添加到结果列表中,一定要new一个，不然后对subset进行操作，结果里面的值也会变。
        }
        //递推开始
        dfs(root.left,target,subset,res);
        dfs(root.right,target,subset,res);
        subset.removeLast();
    }
}
public class 剑指Offer34二叉树中和为某一值的路径 {
    public static void main(String[] args) {

    }
}
